package com.rn.gwt.util.common.client.sort;

import java.util.ArrayList;

import com.google.gwt.core.client.GWT;
import com.rn.gwt.client.lang.reflect.GField;

public class HeapSortAlgorithm extends SortAlgorithm {
   public void sort(ArrayList a,String fieldName,boolean asc,GField field) throws Exception {
    	
    	
    	int N = a.size();
    	for (int k = N/2; k > 0; k--) {
    	    downheap(a, k, N,field);
    	   
            }
    	do {
                Object T = a.get(0);
                replace(a, 0,  a.get(N - 1));
                replace(a,N - 1,T);
                
    	    N = N - 1;
    	   
                downheap(a, 1, N,field);
    	} while (N > 1);
        }

        void downheap(ArrayList a, int k, int N,GField field) throws Exception {
    	Object T = a.get(k - 1);
    	while (k <= N/2) {
                int j = k + k;
                if ((j < N) && compar(a.get(j - 1) , a.get(j), field)<0) {
    	        j++;
    	    }
              
    	    if (compar(T , a.get(j - 1), field)>=0) {
    		break;
    	    } else {
    	    		
    	    	 replace( a,k - 1, a.get(j - 1));
                  
                    k = j;
    	
                }
    	}
    	a.remove(k-1);
            a.add(k - 1, T);
    
        }
        
        
        public void sort(Object[] a,String fieldName,boolean asc,GField field) throws Exception {
        	
        	
        	int N = a.length;
        	for (int k = N/2; k > 0; k--) {
        	    downheap(a, k, N,field);
        	   
                }
        	do {
        		Object T = a[0];
                  a[0] = a[N - 1];
                  a[N - 1] = T;
                  N = N - 1;
      	   
                    
        	    N = N - 1;
        	   
                    downheap(a, 1, N,field);
        	} while (N > 1);
            }

        void downheap(Object[] a, int k, int N,GField field) throws Exception {
        	Object T = a[k - 1];
        	while (k <= N/2) {
                    int j = k + k;
                    if ((j < N) && (compar(a[j - 1] , a[j],field)<0)) {
        	        j++;
        	    }
        	    if (compar(T , a[j - 1],field)>=0) {
        		break;
        	    } else {
                        a[k - 1] = a[j - 1];
                        k = j;
        	
                    }
        	}
                a[k - 1] = T;
        
            }
    }
